#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target);

int main() { return 0; }

vector<vector<int>> fourSum(vector<int>& nums, int target)
{
	vector<vector<int>> res;
	sort(nums.begin(), nums.end());
	for (int k = 0, length = nums.size(); k < length; k++) {
		if (k > 0 && nums[k] == nums[k - 1])
			continue;
		for (int i = k + 1; i < length; i++) {
			if (i > k + 1 && nums[i] == nums[i - 1])
				continue;
			int left = i + 1, right = length - 1;
			while (right > left) {
				// nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
				if (nums[k] + nums[i] > target - (nums[left] + nums[right]))
					right--;
				else if (nums[k] + nums[i] + nums[left] + nums[right] < target) {
					left++;
				} else {
					res.push_back(vector<int> { nums[k], nums[i], nums[left], nums[right] });
					// 去重逻辑应该放在找到一个四元组之后
					while (right > left && nums[right] == nums[right - 1])
						right--;
					while (right > left && nums[left] == nums[left + 1])
						left++;

					// 找到答案时，双指针同时收缩
					right--;
					left++;
				}
			}
		}
	}
	return res;
}
